package com.demo.java.alg.sort;

import com.demo.java.alg.TestBase;

/**
 * 主要是递归思想
 */
public class QuickSort extends TestBase {

    public static void quickSort(int[] arr) {
        quickSort(arr, 0, arr.length - 1);
    }
    public static void quickSort(int[] arr, int start, int end) {
        if (start >= end) {
            return ;
        }
        int l = start, r = end, x = arr[l];
        while (l < r) {
            // 从右边扫描, 查找比参考数小的数
            while (l < r && arr[r] >= x) {
                r--;
            }
            if (l < r) {
                arr[l++] = arr[r];
            }
            // 从左边扫描, 查找比参考数大的数
            while (l < r && arr[l] <= x) {
                l++;
            }
            if (l < r) {
                arr[r--] = arr[l];
            }
        }
        // 设置参考数到'中间'位置(左边比他小, 右边比他大)
        arr[l] = x;
        quickSort(arr, start, l - 1);
        quickSort(arr, l + 1, end);
    }

    public static void main(String[] args) {
        int[] arr = new int[]{5,2,6,0,1,4,3};
        quickSort(arr);
        printArr(arr);
    }

}
